/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2018年08月19日
*   描    述：
*   Copyright (C) 2018 All rights reserved.
*   
================================================================*/


#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    /**
     * @param matrix: A list of lists of integers
     * @param target: An integer you want to search in matrix
     * @return: An integer indicate the total occurrence of target in the given matrix
     */
    int searchMatrix(vector<vector<int>> &matrix, int target) {
        // write your code here
        int m = matrix.size();
        if( m == 0)
            return 0;
            
        int n = matrix[0].size();
        if( n == 0)
            return 0;
            
        int count = 0, i = 0, j = m - 1;
        while( j >=0 && i < n){
            if( matrix[j][i] > target )
                j--;
            else if( matrix[j][i] < target )
                i++;
            else{
                j--;
                count++;
            }
        }

        return count;
    }
};

